class Solution {

    static class TreeNode {
        public int val;
        public TreeNode left;//左孩子的引用
        public TreeNode right;//右孩子的引用

        public TreeNode(int val) {
            this.val = val;
        }
    }
    public TreeNode createTree() {

        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');

        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        //E.right = H;
        return A;
    }
        public int i;

    class Solution {
        public int postIndex;
        public TreeNode buildTree(int[] inorder, int[] postorder) {
            postIndex = postorder.length-1;

            return buildTreeChild(postorder,inorder,0,inorder.length-1);
        }


        private TreeNode buildTreeChild(int[] postorder, int[] inorder,int inBegin,int inEnd) {
            if(inBegin > inEnd) {
                return null;
            }
            //1、创建根节点
            TreeNode root =  new TreeNode(postorder[postIndex]);
            //2. 在中序遍历的字符串当中 找到当前根节点的下标
            int rootIndex = findRootIndex(inorder,inBegin,inEnd,postorder[postIndex]);
            postIndex--;//F
            //3. 分别创建右子树、左子树
            root.right = buildTreeChild(postorder,inorder,rootIndex+1,inEnd);
            root.left = buildTreeChild(postorder,inorder,inBegin,rootIndex-1);
            return root;
        }

        private int findRootIndex(int[] inorder,int inBegin,int inEnd,int key) {
            for(int i = inBegin; i <= inEnd;i++) {
                if(inorder[i] == key) {
                    return i;
                }
            }
            return -1;
        }
    }

}